Bloom Filter

Bloom Filter는 공간 효율적인 확률적 자료구조로, 집합에 특정 요소가 포함되어 있는지 여부를 빠르게 판단할 수 있도록 설계되었습니다. Bloom Filter는 다음과 같은 특성을 가집니다. 1. 확률적 결과 : Bloom Filter는 어떤 요소가 집합에 포함되어 있는지 "확실히" 알고 있는 것은 아니지만, "아니오"라는 답변은 항상 정확합니다. 즉, 요소가 포함되어 있다고 판단할 경우, 실제로 그 요소가 포함되어 있을 가능성이 있지만, 그 가능성이 없는 경우에는 확실하게 제외됩니다. 2. 비트 배열 : 내부적으로 비트 배열을 사용하여 요소를 저장합니다. 각 요소를 추가할 때 여러 해시 함수를 사용해 비트 배열의 여러 위치를 설정합니다. 3. 해시 함수 : 여러 개의 독립적인 해시 함수를 사용해 입력 값을 비트 배열의 인덱스로 변환하고, 이 인덱스에 해당하는 비트를 1로 설정합니다. 새로운 요소가 추가될 때마다 이 해시 함수를 다시 사용하여 비트를 설정합니다. 4. 검색 과정 : 요소를 검색할 때도 동일한 해시 함수를 사용하여 비트 배열의 특정 위치를 확인합니다. 모든 해당 위치의 비트가 1이면 해당 요소가 "존재할 가능성이 있다"고 판단합니다. 하지만 만약 하나라도 0이면, 그 요소는 확실히 존재하지 않는다고 판단합니다. Bloom Filter는 데이터베이스, 웹 캐시, 분산 시스템 등 여러 분야에서 사용되며, 특히 대량의 데이터를 처리하면서 메모리 사용을 최적화하고자 할 때 유용합니다. 단, 요소를 삭제하는 기능은 기본적으로 지원하지 않는다는 단점이 있습니다. 이 문제를 해결하기 위해 Counting Bloom Filter와 같은 변형이 존재합니다.